﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortOf
{
    class Graph
    {
        private const int NUM_VERTICES = 20;
        private Vertex[] vertices;
        private int[,] adjMatrix;
        int numVerts;

        public Graph()
        {
            vertices = new Vertex[NUM_VERTICES];
            adjMatrix = new int[NUM_VERTICES, NUM_VERTICES];
            numVerts = 0;
            for (int j = 0; j < NUM_VERTICES; j++)
            {
                for (int k = 0; k < NUM_VERTICES; k++)
                {
                    adjMatrix[j, k] = 0;
                }
            }
        }

        public void AddVertex(IComparable label)
        {
            vertices[numVerts] = new Vertex(label);
            numVerts++;
        }

        public void AddEdge(int start, int end)
        {
            adjMatrix[start, end] = 1;
            adjMatrix[end, start] = 1;
        }

        public void ShowVertex(int i)
        {
            Console.Write(vertices[i].label.ToString() + " ");
        }

        public void showEdge()
        {
            for (int row = 0; row < numVerts; row++)
            {
                //bool done = false;
                for (int col = 0; col < numVerts; col++)
                {
                    Console.Write(" " + adjMatrix[row, col] + " ");
                }

                Console.WriteLine();
            }
        }

        public int NoSuccessors()
        {
            bool isEdge;
            for (int row = 0; row < numVerts; row++)
            {
                isEdge = false;
                //bool done = false;
                for (int col = 0; col < numVerts; col++)
                {
                    if (adjMatrix[row, col] > 0)
                    {
                        isEdge = true;
                        break;
                    }
                }
                if (!(isEdge))
                {
                    return row;
                }
            }
            return -1;
        }

        public void DelVertex(int vert)
        {
            if (vert != numVerts - 1)
            {
                for (int j = vert; j <= numVerts - 1; j++)
                {
                    vertices[j] = vertices[j + 1];
                    for (int row = vert; row <= numVerts - 1; row++)
                    {
                        MoveRow(row, numVerts);
                        for (int col = vert; col <= numVerts - 1; col++)
                        {
                            MoveCol(row, numVerts - 1);
                        }
                    }
                }
            }
        }

        private void MoveRow(int row, int length)
        {
            for (int col = 0; col <= length - 1; col++)
            {
                adjMatrix[row, col] = adjMatrix[row + 1, col];
            }
        }

        private void MoveCol(int col, int length)
        {
            for (int row = 0; row <= length - 1; row++)
            {
                adjMatrix[row, col] = adjMatrix[row, col + 1];
            }
        }

        public void TopSort()
        {
            int origVerts = numVerts;
            Stack<object> gStack = new Stack<object>();
            while (numVerts > 0)
            {
                int currVertex = NoSuccessors();
                Console.WriteLine(currVertex.ToString());
                if (currVertex == -1)
                {
                    Console.WriteLine("Error: graph has cycles.");
                    return;
                }
                gStack.Push(vertices[currVertex].label);
                DelVertex(currVertex);
            }
            Console.Write("Toplogical sorting order: ");
            while (gStack.Count > 0)
            {
                Console.Write(gStack.Pop() + " ");
            }
        }
    }
}
